package com.jumper.cwolf.leetcode;

import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * 描述：
 *
 * @author cwolf
 * @version 1.0
 * @date 2021/4/2 11:18
 */
public class Code1721 {

    public int trap(int[] height) {
        if(height.length<2){
            return 0;
        }
        int max = maxRight(height,0);
        int maxRight = maxRight(height, max+1);
        int computeRight = computeRight(height, max, maxRight, 0);
        int maxLeft = maxLeft(height,max);
        int computeLeft = computeLeft(height, maxLeft, max, 0);
        return computeLeft+computeRight;
    }

    public int computeRight(int[] height ,int start,int end,int totals){
        if(start==end){
            return totals;
        }
        int h = end-start-1;
        int w = height[end];
        int total = h*w-getSum(height,start+1, end);
        totals+=total;
        int max = maxRight(height,end+1);
        if(max==end||max==0){
            return totals;
        }
        return computeRight(height,end,max,totals);
    }


    public int computeLeft(int[] height ,int start,int end,int totals){
        if(end==0||start==end){
            return totals;
        }
        int h = end-start-1;
        int w = height[start];
        int total = h*w-getSum(height,start+1, end);
        totals+=total;
        int max = maxLeft(height,start);
        if(max==end){
            return totals;
        }
        return computeLeft(height,max,start,totals);
    }


    public int getSum(int[] height,int start,int end){
        int t = 0;
       for(int i=start;i<end;i++){
           t+=height[i];
       }
       return t;
    }

    public int maxRight(int[] height,int point ){
        if(point>=height.length){
            return height.length-1;
        }
        int index = 0;
        int before = height[point];
        for (int i=point;i<height.length;i++){
            int h = height[i];
            if(h>=before){
                index = i;
                before = h;
            }
        }
        return index;
    }

    public int maxLeft(int[] height ,int point ){
        if(point<=0){
            return 0;
        }
        int index = 0;
        int before = 0;
        for (int i=0;i<point;i++){
            int h = height[i];
            if(h>before){
                index = i;
                before = h;
            }
        }
        return index;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{
                5,5,1,7,1,1,5,2,7,6
        };
        int trap = new Code1721().trap(arr);
        System.out.println(trap);
    }

}
